package com.study.algorithm;

public class SearchAlgorithm {

	public static void main(String[] args) {
		int a[]= {1,3,4,5,6,8,8,8,11,18};
		System.out.println(bsearch(a, 10, 8));
		System.out.println(bsearch2(a, 10, 8));
	}
	
	/**
	 * 二分查找：查找第一个出现8的数组下标（写法1）
	 * @param a
	 * @param n
	 * @param value
	 * @return
	 */
	public static int bsearch(int[] a, int n, int value) {
		  int low = 0;
		  int high = n - 1;
		  while (low <= high) {
		    int mid = low + ((high - low) >> 1);
		    if (a[mid] >= value) {
		      high = mid - 1;
		    } else {
		      low = mid + 1;
		    }
		  }

		  if (low < n && a[low]==value) return low;
		  else return -1;
		}
	/**
	 * 二分查找：查找第一个出现8的数组下标（写法2）
	 * @param a
	 * @param n
	 * @param value
	 * @return
	 */
	public static int bsearch2(int[] a, int n, int value) {
		  int low = 0;
		  int high = n - 1;
		  while (low <= high) {
		    int mid =  low + ((high - low) >> 1);
		    if (a[mid] > value) {
		      high = mid - 1;
		    } else if (a[mid] < value) {
		      low = mid + 1;
		    } else {
		      if ((mid == 0) || (a[mid - 1] != value)) return mid;
		      else high = mid - 1;
		    }
		  }
		  return -1;
		}


}
